#pragma once

#include "utility.h"
#include "list.h"
#include "unordered_map.h"

namespace qyc
{
    template<class K, class V>
    class LRUCache
    {
        typedef pair<K, V> data_type;
        typedef typename list<data_type>::iterator list_ptr;
        typedef LRUCache<K, V> self;
    public:
        LRUCache(size_t capacity)
            : _capacity(capacity)
        {}

        pair<V, bool> get(const K& key)
        {
            typename unordered_map<K, list_ptr>::iterator it = _hashmap.find(key);
            if (it != _hashmap.end())
            {
                _list.splice(_list.begin(), _list, it->second);
                return pair<V, bool>(it->second->second, true);
            }
            return pair<V, bool>(V(), false);
        }

        void put(const K& key, const V& value)
        {
            typename unordered_map<K, list_ptr>::iterator it = _hashmap.find(key);
            if (it != _hashmap.end())
            {
                it->second->second = value;
                _list.splice(_list.begin(), _list, it->second);
            }
            else
            {
                if (_hashmap.size() == _capacity)
                {
                    int del = _list.back().first;
                    _list.pop_back();
                    _hashmap.erase(del);
                }
                _list.push_front(pair<K, V>(key, value));
                _hashmap[key] = _list.begin();
            }
        }
        
        void swap(self& right)
        {
            _hashmap.swap(right._hashmap);
            _list.swap(right.swap);
            qyc::swap(_capacity, right._capacity);
        }
    private:
        unordered_map<K, list_ptr> _hashmap;
        list<data_type> _list;
        size_t _capacity;
    };
}